1. Field of the Invention
The present invention relates to communications networks and, more particularly, to a method of selecting a least weight route between two end stations, or end nodes, in the network.
2. Description of Prior Art
For purposes of the following descriptions, a communications network can be generally defined as a collection of network nodes and end nodes, or end stations, interconnected through communications links. A network node can be characterized as a data processing system that provides certain functions within the network, such as routing of messages between itself and its adjacent, or neighboring, nodes, selection of routes for messages to be transmitted between two nodes, and the furnishing of directory services to connected end nodes. The link between nodes may be permanent communications links, such as conventional cable connections or links, that are enabled only when needed, such as dial-up telephone connections. End nodes are exemplified by devices, such as display terminals, intelligent workstations, printers, and the like, which do not provide routing or route selection or directory services to other nodes in the network. Collectively, the network nodes, the end nodes and the links between the nodes are referred to as network resources. The physical configuration and characteristics of the various nodes and links in a network are said to be the topology of the network.
For a user at one end node to exchange data with another user at another end node, a path, or route, must be set up through the network. The route will include the end node at which the first user is located (the source end node), the end node at which the second user is located (the destination end node), possibly one or more network nodes and the links, or transmission groups, which connect the nodes on the route. A transmission group is normally defined as a set of parallel links with similar characteristics that form a single logical link that has a higher capacity than each of the individual links in the group. For purposes of the following discussion, it should be assumed that the term transmission group can also contemplate a single physical link. The terms are used interchangeably in the following description.
In an ideal network, data provided by a first user is transmitted to a second user at no cost, with zero delays, with perfect reliability, and with complete security regardless of how many nodes and transmission groups might be included in the route between the two users. Unfortunately, real data communications networks lack these ideal characteristics. Varying amounts of delays may be introduced over different routes. Some types of transmission groups may cost more to use, or introduce more delay than others. The integrity of transmitted data may be protected better on some transmission groups than others. Other "imperfections" not even discussed above exist in a real network.
Because nodes and transmission groups in a real network possess different characteristics, it is a common practice to assign weights to both nodes and transmission groups, and to use the assigned weights in computing an optimal, or least, weight route through the network from one user to another. The weight generally reflects how closely a given node, or transmission group, meets a predetermined standard of performance. For example, if weights were to be assigned on the basis of delay characteristics alone, a high-delay transmission group would have a greater assigned weight than a low-delay transmission group.
In U.S. Pat. No. 4,873,517, entitled "Method For Selecting Least Weight End Node to End Node Route In A Data Communication Network" and issued to A. E. Baratz et al, a "best" route, through a network from a first user at one end node, or end station, to a second user at another end node, or end station, is determined by summing the weight of nodes and transmission groups in various potential routes. The route having the lowest total weight, which is understandably referred to as the least-weight route, is considered to be the "best" route between the users.
When a first user requests that a path be established through the network to a second user, information as to the characteristics of the transmission groups connecting both user's end nodes to network nodes is furnished by the user's end nodes to the network node responsible for the route computation. This network node calculates an optimal route through the network in a staged process. First, the information received from the end nodes is used to calculate optimal routes from the end nodes to all network nodes to which those end nodes are connected. Next, the network node uses information stored in its own network topology database to calculate optimal routes from a first set of network nodes to a second set of network nodes. The first set of network nodes is all network nodes connected to the first user's end node. The second set of network nodes is all network nodes connected to the second user's end node. The results of the end node to network node calculations and network node to network node calculations are concatenated, or combined, to determine the optimal end node to end node route through the network.
FIG. 1 is an example of a communication network from the Baratz et al patent. The illustrated network includes a plurality of network nodes NNA, NNB, NNC, NND, NNE and NNF. The various network nodes are interconnected by transmission groups illustrated only as single lines. A number of end nodes, EN1 through EN10, are connected to various ones of the network nodes. Certain end nodes may be connected to more than one network node, and/or may have parallel transmission groups to the same network node. For example, end node EN2 is connected to both network node NNA and NNB with two parallel transmission groups to network node NNB. Similarly, end node EN6 is connected to both network nodes NND and NNF with three parallel transmission groups to node NNF.
As mentioned above, weights are assigned to each transmission group and network node in the network. These weights represent the "cost" of using the node, or transmission group, to transmit data. In the figure, the weights are represented by numerals either appearing within the symbol for the network node, or adjacent the line representing the transmission group connecting the network nodes. The weight values themselves appearing in the figure are arbitrarily selected for purposes of illustration, and should not be interpreted as actual numerical values that would be assigned in a typical date communications network. The figure also shows weights assigned to transmission groups connecting end nodes to their adjacent network nodes. While the weights assigned to the end node transmission groups are known to the end nodes, they may not be known to the network nodes if the network nodes maintain a topology database containing only information about the network nodes themselves and the transmission groups which interconnect the network nodes. While the information stored in the network nodes is adequate to allow the network nodes to compute optimal routes between any two network nodes, it is not adequate to permit a network node to compute an optimal route between two end nodes.
To allow a network node to compute an optimal end node to end node route, information about the transmission groups connecting the end nodes to adjacent network nodes must be made available to the network node responsible for the route computation. The prior art process for making such information available is described with reference to FIG. 2 from the Baratz et al patent. FIG. 2 is a time-based chart of messages which flow through the network when a user located at an end node EN2 desires to communicate with a user located at end node EN6. The source end node EN2 sends a Message Unit (MU) to the network node NNB having responsibility for providing routing services to EN2. The message includes information, or vectors, about the transmission groups which connect EN2 to both NNA and NNB. The transmission group vectors are saved at NNB, and the message is forwarded through the network via nodes NNC and NNF to end node EN6. End node EN6 responds with a Message Unit Reply (MUR) including information about the transmission groups which connect end node EN6 to its two adjacent network nodes, NND and NNF. The reply is forwarded through the network to the serving network node NNB, which saves the destination transmission group vectors.
Network node B then has the information it needs to compute an optimal route through the network between the origin end node EN2 and the destination end node EN6. As mentioned earlier, the computations are staged with the optimal end node to network node routes being computed separately from the routes between network nodes. All of the computations for determining best route take place in network node B.